%% Author: vjache
%% Created: 04.02.2010
%% Description: TODO: Add description to ring
-module(ring).

%%
%% Include files
%%
-include_lib("eunit/include/eunit.hrl").
%%
%% Exported Functions
%%
-export([new/0,
		 new/2,
		 add_list/2,
		 dump/1,
		 route/2,
		 route_list/2,
		 remove_list/2,
		 targets/1,
		 default_hasher/1,
		 default_decorator/1,
		 distribution/2,
		 distribution_test/1]).

-record(ring,{hash_fun,decor_fun,gbtree}).

%%
%% API Functions
%%
new() ->
	new(fun default_hasher/1,fun default_decorator/1).
new(HashFun,DecorFun) when 
  is_function(HashFun,1),is_function(DecorFun,1) ->
	#ring{hash_fun=HashFun,decor_fun=DecorFun,gbtree=gb_trees:empty()}.

add_list(Ring,[])->
	Ring;
add_list(Ring,TargetList) when 
  is_record(Ring,ring),is_list(TargetList) ->
	HashFun=Ring#ring.hash_fun,
	DecorFun=Ring#ring.decor_fun,
	Tree1=lists:foldl(
	  fun(Target,Tree)->
			  lists:foldl(
				fun(Key,Tr)->
						gb_trees:enter(HashFun(Key), Target, Tr)
				end, Tree, DecorFun(Target))
	  end, 
	  Ring#ring.gbtree, TargetList),
	Ring#ring{gbtree=Tree1}.
remove_list(Ring,[]) ->
	Ring;
remove_list(Ring,TargetList) when 
  is_record(Ring,ring),is_list(TargetList) ->
	HashFun=Ring#ring.hash_fun,
	DecorFun=Ring#ring.decor_fun,
	Tree1=lists:foldl(
	  fun(Target,Tree)->
			  lists:foldl(
				fun(Key,Tr)->
						gb_trees:delete_any(HashFun(Key), Tr)
				end, Tree, DecorFun(Target))
	  end, 
	  Ring#ring.gbtree, TargetList),
	Ring#ring{gbtree=Tree1}.
route(Ring,Key)->
	HashFun=Ring#ring.hash_fun,
	Gbt={Size,Tree}=Ring#ring.gbtree,
	if Size==0 -> throw(ring_empty);
	   true ->
		   KeyHash=HashFun(Key),
		   case gbt_ring_seek(KeyHash,Tree,smallest) of
			   smallest -> {_K,V}=gb_trees:smallest(Gbt),V;
			   Route -> Route
		   end
	end.
route_list(Ring,KeyList) when is_list(KeyList)->
	[{Key,route(Ring,Key)}||Key<-KeyList].

targets(Ring) ->
	Tree=Ring#ring.gbtree,
	sets:to_list(sets:from_list(gb_trees:values(Tree))).

dump(Ring)->
	gb_trees:to_list(Ring#ring.gbtree).

distribution(Ring,ValueList) when is_list(ValueList) ->
	dict:to_list(lists:foldl(
	  fun({_Value,Target},Dict)->
			  dict:update_counter(Target, 1, Dict)
	  end, dict:new(), route_list(Ring, ValueList)));
distribution(Ring,Max) when is_integer(Max) ->
	Tree=Ring#ring.gbtree,
	L=gb_trees:to_list(Tree),
	{_,Dict1}=lists:foldl(
				fun({H,T},{H0,Dict})->
						{H,dict:update_counter(T, H-H0, Dict)}
				end, {0,dict:new()}, L),
	[{_,T}|_]=L,
	{H,_}=lists:last(L),
	Dict2=dict:update_counter(T, Max-H, Dict1),
	dict:to_list(Dict2).

default_decorator(Value) ->
	decor(Value,50,[]).
decor(_Value,0,Result)->
	Result;
decor(Value,N,Result)->
	decor(Value,N-1,[{Value,N}|Result]).
%% 	[Value,
%% 	 {Value,"one"},
%% 	 {Value,"two"},
%% 	 {Value,"three"},
%% 	 {Value,"four"},
%% 	 {Value,"five"},
%% 	 {Value,"six"},
%% 	 {Value,"seven"},
%% 	 {Value,"eght"},
%% 	 {Value,"nine"},
%% 	 {Value,"ten"}].
default_hasher(Value) ->
	erlang:phash2({"976",Value},10000000).
%%
%% Local Functions
%%
gbt_ring_seek(KeyHash,{K,_V,_Sm,Bg}=_Tree,Res) when KeyHash>K ->
	gbt_ring_seek(KeyHash,Bg,Res);
gbt_ring_seek(KeyHash,{K,V,Sm,_Bg}=_Tree,_Res) when KeyHash<K ->
	gbt_ring_seek(KeyHash,Sm,V);
gbt_ring_seek(KeyHash,{K,_V,_Sm,_Bg}=_Tree,Res) when KeyHash==K ->
	Res;
gbt_ring_seek(_KeyHash,nil,Res) ->
	Res.

%%
%% eUnit test functions
%%

simple_test() ->
	R=new(fun default_hasher/1,fun default_decorator/1),
	R1=add_list(R,[alfa,beta,gamma,delta]),
	{R1,route_list(R1,"qwertyuiop[]asdfghjkl;'zxcvbnm,.")}.
distribution_test(Data) when is_list(Data) ->
	R=new(fun default_hasher/1,fun default_decorator/1),
	R1=add_list(R,[alfa,beta,gamma,delta]),
	{R1,distribution(R1,Data)}.